export function search(nums: number[], target: number): number {
    return binarySearch(nums, target, 0, nums.length-1);
};

function binarySearch(nums: number[], target: number, start: number, end: number): number {
    if (start >= end) {
        if (nums[start] === target) return start;
        return -1;
    }

    const midIdx = ((end - start)>>1) + start;
    if (nums[midIdx] > target) {
        return binarySearch(nums, target, start, midIdx);
    } else if (nums[midIdx] < target) {
        return binarySearch(nums, target, midIdx+1, end);
    } else {
        return midIdx;
    }
}